package pojo

/*

getSize()  返回堆的长度
isEmpty()  判断数组
heapUp()
heapDown()如何取出大根堆的头结点？取出头节点，把最后一个节点的数放在头结点上，heapSize减1。然后把头结点的数和两个子节点中最大的数比较，
比较大子节点还大就交换位置，以此操作，直至没有子节点或者比子节点都小。这个过程叫做heapify.
add()加入
poll()弹出
*/

type Heapp struct {
	heapSize int
	array    []int
}

func NewHeapp() Heapp {
	return Heapp{
		heapSize: 0,
		array:    make([]int, 100),
	}
}

func (h *Heapp) GetSize() int {
	return h.heapSize
}
func (h *Heapp) IsEmpty() bool {
	return h.heapSize == 0
}
func (h *Heapp) HeapUp(index int) {
	if index < 0 {
		return
	}
	father := (index - 1) / 2
	for father >= 0 {
		if h.array[father] > h.array[index] {
			h.array[father], h.array[index] = h.array[index], h.array[father]
			index = father
			father = (index - 1) / 2
		} else {
			return
		}
	}
}
func (h *Heapp) HeapDown(index int) {
	if index < 0 {
		return
	}
	leftChild := index*2 + 1

	for leftChild < h.heapSize {
		min := leftChild
		if (h.array[leftChild] > h.array[leftChild+1]) && (leftChild+1) < h.heapSize {
			min = leftChild + 1
		}
		if h.array[min] > h.array[index] {
			min = index
		}

		if min == index {
			break
		}

		h.array[min], h.array[index] = h.array[index], h.array[min]
		index = min
		leftChild = index*2 + 1
	}

}

func (h *Heapp) Add(value int) {
	h.array[h.heapSize] = value
	h.heapSize++
	h.HeapUp(h.heapSize - 1)
}
func (h *Heapp) Peek() int {
	return h.array[0]
}

func (h *Heapp) Poll() int {
	min := h.array[0]
	h.array[h.heapSize-1], h.array[0] = h.array[0], h.array[h.heapSize-1]
	h.heapSize--
	h.HeapDown(0)

	return min
}

type Line struct {
	Start int
	End   int
}

func NewLine(Start, End int) *Line {

	return &Line{
		Start: Start,
		End:   End,
	}
}

type Lines []*Line

func (l Lines) Len() int {
	return len(l)
}
func (l Lines) Swap(i, j int) {
	l[i], l[j] = l[j], l[i]
}
func (l Lines) Less(i, j int) bool {
	return l[i].Start < l[j].Start
}
